import java.util.LinkedList;
import java.util.List;

public class Solution {
    public static int LastRemaining_Solution1(int n, int k) {
        if(n<1||k<1){
            return -1;
        }
        //用linkedlist 链表，删除第k个数
        List<Integer> list = new LinkedList<>();
        for(int i=0; i<n; i++){
            list.add(i);
        }
        int index = 0;
        while(list.size()>1){
            index = (k-1+index)%list.size();//每次从上次删除的位置开始数k个数，删除
            list.remove(index);
        }
        return list.get(0);
    }
    public static int LastRemaining_Solution2(int n, int k) {
        if(n<1||k<1){
            return -1;
        }
        if(n==1)
            return 0;
        return (LastRemaining_Solution2(n-1,k)+k)%n;
    }

    public static void main(String args[]){
        int b = LastRemaining_Solution2(6,3);
        System.out.println(b);
    }
}

